Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Constraints:

• 1 <= strs.length <= 200

• 0 <= strs[i].length <= 200

• strs[i] consists of only lowercase English letters if it is non-empty.

My Solution

One of the first things to realize in solving this problem is the constraints. The strs array will not be more than 200 elements and each string in strs will not be longer than 200 characters. This means it’s feasible to keep track of the counts of all the prefix substrings in strs. We can use a HashMap for this. Once we’ve stored the counts of all the substrings, we can iterate through each substring in the HashMap and keep track of the longest substring that is present in all the strings in strs (that is it has a count of n, where n is the number of elements in strs). This is the string we return.

Iterating and storing the counts of all the substrings is O(m*n) time complexity, where m is the length of the longest string in strs and n is the number of elements in strs. Then iterating through all substrings again is O(m*n), since there are m*n strings in our HashMap. The space complexity would be O(m²n), since for each string in strs, we store m substrings of length 1, 2, 3, … m and we do this for n elements.

class Solution {
    public String longestCommonPrefix(String[] strs) {
        Map<String,Integer> counts = new HashMap<>();
        int n                      = strs.length;
        int max                    = 0;
        String max_string          = "";

        for (int i = 0; i < n; i++) {
            String s = strs[i];
            for (int j = 1; j <= s.length(); j++) {
                String sub = s.substring(0, j);
                counts.put(sub, counts.getOrDefault(sub,0)+1);
            }
        }

        for (String s : counts.keySet()) {
            if (counts.get(s) == n && s.length() > max) {
                max = s.length();
                max_string = s;
            }
        }

        return max_string;
    }
}